Problem statement: zenit14kkf

Ku každej správnej usadlosti patrí aj miesto, kde sa zvieratká môžu stretávať a žiť svoj sociálny život. Aby si svoje námestie skrášlili, rozhodli sa vybudovať dekoratívny monument. Táto stavba pozostáva z piedestálu štvorcového tvaru, na ktorom sú rozmiestnené stĺpy rôznej výšky. Pôdorys je rozdelený na malé štvorčeky. Každý má buď základnú výšku piedestálu 1, alebo je na ňom stĺp.

Štruktúru si môžeme definovať rekurzívne pre rôzne levely. Štruktúra levelu \(L\) vznikne spojením štyroch štruktúr levelu \(L-1\). Nasleduje príklad pre levely 1, 2 a 3:

1

1 1 1
1 2 1
1 1 1

1 1 1 1 1 1 1
1 2 1 1 1 2 1
1 1 1 1 1 1 1
1 1 1 3 1 1 1
1 1 1 1 1 1 1
1 2 1 1 1 2 1
1 1 1 1 1 1 1

Vo všeobecnosti má štruktúra levelu \(L\) dvakrát toľko riadkov a stĺpcov ako štruktúra levelu \(L-1\) a ešte jeden riadok aj stĺpec navyše. Prostredný riadok aj stĺpec je vyplnený jednotkami, s výnimkou úplne stredného políčka, kde je stĺp s výškou \(L\).

Na vstupe je celé číslo medzi 2 a 9 vrátane. Na výstup vypíšte pôdorys monumentu daného levelu. Medzi susednými číslami vypíšte medzeru. Na konci riadku medzeru nevypisujte.

Príklady

Input:

2

Output:

1 1 1
1 2 1
1 1 1

Input:

3

Output:

1 1 1 1 1 1 1
1 2 1 1 1 2 1
1 1 1 1 1 1 1
1 1 1 3 1 1 1
1 1 1 1 1 1 1
1 2 1 1 1 2 1
1 1 1 1 1 1 1